Bloom Filters

A Bloom filter is useful when a fast “definitely absent” answer can avoid an expensive lookup. It uses little memory but may return false positives, so a “possibly present” answer still needs verification.